\input{euler.tex}

\begin{document}

\problem[100]{Exactly 50\% Chance of Taking Two Blue Discs}

If a box contains 21 colored discs, composed of 15 blue discs and 6 red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, $P(BB) = (15/21)(14/20) = 1/2$.
 
The next such arrangement, for which there is exactly 50\% chance of taking two blue discs at random, is a box containing 85 blue discs and 35 red discs.
 
By finding the first arrangement to contain over $10^{12}$ discs in total, determine the number of blue discs that the box would contain.

\solution

Let $n$ be the total number of discs, and $b$ be the number of blue discs. The probability of drawing two blue discs is
\begin{equation}
P = \frac{b(b-1)}{n(n-1)} = \frac12 . \label{eq:100.1}
\end{equation}
This equation can be rearranged as
\begin{equation}
(2n-1)^2 - 2(2b-1)^2 = -1 . \label{eq:100.2}
\end{equation}
Substituting $x=2n-1$ and $y=2b-1$, we get the standard \emph{Pell equation}
\begin{equation}
x^2 - 2 y^2 = -1 . \label{eq:100.3}
\end{equation}

Obviously $(x_0,y_0) = (1,1)$ is a fundamental solution to equation \eqref{eq:100.3}. The rest solutions can be generated from this fundamental solution by noting that
\begin{align}
(x_0 + y_0 \sqrt{2})^2(x_0 - y_0 \sqrt{2})^2 &= 1 \notag \\
(x + y \sqrt{2})(x - y \sqrt{2}) &= -1 \notag \\
(x' + y' \sqrt{2})(x' - y' \sqrt{2}) &= -1 \notag 
\end{align}
and requiring that
\[
(x' + y' \sqrt{2}) = (x + y \sqrt{2}) (x_0 + y_0 \sqrt{2})^2 .
\]
The result is the following recursive relation:
\begin{align}
x' &= x(x_0^2+2 y_0^2) + y (4 x_0 y_0) \notag \\
y' &= y(x_0^2+2 y_0^2) + x (2 x_0 y_0) \notag .
\end{align}
For this problem, we iterate the solutions until $n = (1+x)/2$ is big enough. Then it follows immediately that $b = (1+y)/2$.

\answer

756872327473

\complexity

Time complexity: $\BigO(\ln n)$

Space complexity: $\BigO(1)$

\reference

http://mathworld.wolfram.com/PellEquation.html

http://en.wikipedia.org/wiki/Pell's\_equation

\end{document} 